// Copyright 2011 Jefferson Willian
// willmont7@gmail.com

#include <cstdio>

#define MAX 3000
#define INF 100000000

/* Verifica se o intervalo init-end da string str eh um palindromo */
bool isPalin(char str[], int init, int end) {
  if (end == init)
    return true;

  ++end;
  int middle = (end+init)/2;

  for (int i = init;i < middle;i++)
    if (str[i] != str[end-1-(i-init)])
      return false;

  return true;
}

int main() {
  int n;
  int t1, t2;
  int games = 1;
  char str[MAX];
  int din[MAX];    // Matriz auxiliadora para prog. dinamica

  while (scanf("%d", &n) && n != 0) {
    getchar();
    gets(str);

    for (int i = 0;i < n;i++)
      din[i] = INF;

    din[n] = 0;
    din[n-1] = 1;

    if (isPalin(str, 0, n-1)) {
      din[0] = 1;
      goto end;
    }

    /* Comeca da antes da ultima letra e a partir dela faz uma  */
    /* busca comecando pela ultima letra e verificando se forma */
    /* um palindromo, e se essa eh a melhor solucao do problema */
    for (int i = n-2;i >= 0;--i)
      for (int j = n-1;j >= i;--j)
        if (isPalin(str, i, j)) {
          /* Verifica se eh melhor usar o palindromo ou nao       */
          /* buf[j+1]+1 -> Um palindromo mais o q foi processado  */
          /* a partir de j+1                                      */
          /* buf[i] -> O que foi processado ate i                 */
          din[i] = din[j+1]+1 < din[i]? din[j+1]+1:din[i];
          /* Solucao otima(formar um palindromo com todos as letras  */
          /* ou formar dosi palindromos quando nao processa ate      */
          /* ate a ultima letra                                      */
          /* Obs.: Essa otimizacao foi necessaria para passar no     */
          /* tempo exigido                                           */
          if (din[i] == 1 || (din[i] == 2 && j < n-1))
            break;
        }

    end:

    printf("Teste %d\n%d\n\n", games++, din[0]);
  }

  return 0;
}
